For the Backtracking-based Iterative Hard Thresholding algorithm (BIHT) has the problems of large number of iterations and too long reconstruction time, a Backtracking-based Conjugate Gradient Iterative Hard Thresholding algorithm (BCGIHT) was proposed. Firstly, the idea of backtracking was adopted in each iteration, and the support set of the previous iteration was combined with the current support set to form a candidate set. Then, a new support set was selected in the space spanned by the matrix columns corresponding to the candidate set, so as to reduce times that the support set was selected repeatedly and ensure that the correct support set was found quickly. Finally, according to the criteria of whether or not the support set of the last iteration was equal to the support set of the next iteration, gradient descent method or conjugate gradient method was used to be the optimization method, so as to accelerate the convergence of algorithm. The reconstruction experimental results of one-dimensional random Gaussian signals show that, the reconstruction success rate of BCGIHT is higher than that of BIHT and similar algorithms, and its reconstruction time is less than that of BIHT by at least 25%. The reconstruction experiment results of Pepper image show that, the reconstruction accuracy and the anti-noise performance of the proposed BCGIHT algorithm is comparable with BIHT and similar algorithms, and its reconstruction time is reduced by more than 50% compared with BIHT.